#include <cstdio>
#include <cstdlib>

typedef long long ll;
typedef unsigned long long ull;
int t, p[8] = {2, 3, 5, 7, 11, 13, 17, 19};
ll n, maxfactor;

inline ll qmul(ll a, ll b, ll mod) {
  ll c = a * b - (ll)((long double)a * b / mod) * mod;
  return c < 0 ? c + mod : (c >= mod ? c - mod : c);
}

inline ll qpow(ll base, ll exp, ll mod) {
  ll res = 1;
  while (exp) {
    if (exp & 1) res = qmul(res, base, mod);
    base = qmul(base, base, mod);
    exp >>= 1;
  }
  return res;
}

inline bool check(int a, ll md, ll exp) {
  static ll tmp;
  if ((tmp = qpow(a, exp, md)) == md - 1) return true;
  if (tmp == 1) return exp & 1 ? true : check(a, md, exp >> 1);
  return false;
}

inline bool miller(ll x) {
  if (x == 2) return true;
  if ((x & 1) == 0 || x == 1) return false;
  for (int i = 0; i < 8; ++i) {
    if (x == p[i]) return true;
    if (!check(p[i], x, x - 1)) return false;
  }
  return true;
}

inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

inline ll f(ll x, const ll& c, const ll& n) { return (qmul(x, x, n) + c) % n; }

inline ll pollardRho(ll x) {
  ll s = 0, t = 0, c = 1ll * rand() << 30 ^ rand() % x, val = 1, d;
  for (int k = 1;; val = 1, s = t, k <<= 1) {
    for (int i = 0; i < k; ++i) {
      t = f(t, c, x);
      val = qmul(val, std::abs(t - s), x);
      if (i % 127 == 0) {
        d = gcd(val, x);
        if (d != 1) return d;
      }
    }
    d = gcd(val, x);
    if (d != 1) return d;
  }
}

inline void divide(ll x) {
  if (x <= maxfactor || x < 2) return;
  if (miller(x)) return maxfactor = maxfactor > x ? maxfactor : x, void();
  ll p;
  do { p = pollardRho(x); } while (p == x);
  while (x % p == 0) x /= p;
  divide(x), divide(p);
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("Pollard-Rho.in", "r", stdin);
  freopen("Pollard-Rho.out", "w", stdout);
#endif
#endif

  scanf("%d", &t);
  while (t--) {
    srand((unsigned long long)new bool);
    scanf("%lld", &n);
    maxfactor = 0;
    divide(n);
    if (maxfactor == n) puts("Prime");
    else
      printf("%lld\n", maxfactor);
  }
  return 0;
}